Crossing Number

Definition / 定义

（主要用于图论与结论/结理论）交叉数：在满足规则的图形表示中，把边（或绳结线段）画在平面上时，不可避免的最少交叉点数量。

• 在图论中：指某个图在平面绘制时，边与边的最小交叉次数。
• 在结论中：指某个结的平面图中最少的交叉点数。（此义也很常见）

Pronunciation / 发音

/ˈkrɔːsɪŋ ˈnʌmbər/

Examples / 例句

The crossing number of this graph is 1.
这个图的交叉数是 1。

Determining the crossing number is NP-hard for general graphs, so researchers often use bounds and heuristics.
对于一般图而言，确定交叉数是 NP-困难的，因此研究者常用上下界估计与启发式方法。

Etymology / 词源

crossing 来自 cross（交叉）+ -ing（名词化，表示“交叉这一行为/结果”）；number 源自拉丁语 numerus（数目），经由法语进入英语。作为术语，“crossing number”在 20 世纪的图论与结论研究中逐渐固定，用来表示“最少交叉次数”的量。

Related Words / 相关词

• Planar
• Planarity
• Embedding
• Graph
• Edge
• Vertex
• Intersection
• Knot

Literary Works / 文学作品

• Graph Drawing: Algorithms for the Visualization of Graphs（Di Battista 等）：讨论图绘制中的交叉最小化等问题，涉及 crossing number 的概念与相关结果。
• Introduction to Graph Theory（Douglas B. West）：在平面图与相关章节中提及交叉与交叉数思想（常以交叉最少的绘制为目标）。
• Graph Theory（Bondy & Murty）：涵盖平面性与图的嵌入等主题，交叉数作为相关概念在研究与习题语境中出现。